Двудольный граф

Определение:

Пусть в графе $G = (X, Y, E)$ множество вершин $V = X \cup Y$ и $X \cap Y = \varnothing$. $X$ и $Y$ называются **долями графа**, и вершины, принадлежащие одной и той же доле, попарно несмежны.

Связь с деревом

Формулировка:

Любое дерево — двудольный граф.

Д-во:

В первую долю входит корень и все вершины, в которые из корня ведет путь четной длины, а во вторую остальные вершины.